1. Field of the Invention
The present invention relates in general to multiple-pattern sequence generators based on inverting non-linear autonomous machines. In particular, the present invention relates to multiple-pattern sequence generators based on inverting non-linear autonomous machines, capable of relying on the interdependency between deterministic patterns in a sequence for generating a multiple of patterns in a sequence containing the leading deterministic patterns and followed by pseudo-random patterns. More particularly, the present invention relates to multiple-pattern sequence generators based on inverting non-linear autonomous machines having simplified hardware structural configuration.
2. Technical Background
Sequence generators are widely utilized in digital electronic equipments such as controllers, coders, decoders, and test-pattern generators etc. The principal hardware structural configuration of some of the conventional sequence generators are based on digital counters which enjoy the primary advantage of simplicity in their electronic circuitries. However, they suffer the major limitation in the generation of fixed sequences.
Others of the conventional sequence generator employ finite state machines for the description of the interdependent relationship between the sequences and utilize random logic to construct the circuitry for the generation of the desired sequences. The advantage of this implementation is the ability to generate any specific sequence, but with the obvious disadvantage of the lack of regularity in the constructed circuitries. Such circuitries are also inadequate for the generation of pseudo-random sequences.
Still other conventional sequence generators employ the category of linear feedback shift registers (LFSR) as the primary core for the generation of pseudo-random sequences. Maximum lengths of pseudo-random sequences can be advantageously generated with simple and regular hardware structural configurations. However, the generated sequences are not in arbitrary order, but are restricted by the feedback path in the LFSR's.
Specific deterministic patterns in the generated sequences for practical applications are frequently required to appear as early as possible, or, they may also be required to appear repeatedly, or in specific order in the generated pseudo-random sequences. These conditions are not totally satisfiable with the conventional state-of-the-art and straight-forward LFSR's. With the LFSR being widely employed in the generation of pseudo-random sequences having maximized lengths, reseeding practices of the LFSR's are utilized to change the order of the patterns in the generated sequences, causing the desired pattern to appear as early as possible. Alteration of the feedback paths in the LFSR's can result in the change of the appearing order of the patterns in the generated sequences, thereby generating some of the required specific patterns. However, unless certain stored-pattern procedures are taken to pre-store ordered sequences or specific sequences in memory devices before LFSR's can be used to generate the pseudo-random sequence, current LFSR techniques can only satisfy some of the practical application requirements. Otherwise, instead of simplicity and regularity, huge and complex hardware configuration will be necessary for the generation of the practically arbitrary sequences of repeated and pseudo-random nature.
One important application of multiple-pattern sequence generator is in the testing of very large-scale integrated circuit (VLSI) devices. VLSI technology is advancing rapidly, electronic circuitries with complex functionality and huge scale of integration are being integrated into single IC packages. These VLSI IC packages do not have sufficient lead pins for the arrangement of the connection to external testing equipment for the IC device testing purposes. Internal testing circuitries are therefore included as a portion of the entire IC device for conducting on-board testing from inside the VLSI IC device. This built-in self-test (BIST) technique has being widely accepted not only because it reduces the cost and difficulty of the external testing practice, but also because of its ability to provide the real-time on-line testing of the VLSI device.
In a typical BIST design, a sequence generator is required for the generation of a test sequence containing necessary testing patterns. As is in the case of the above-discussed sequence generators, most BIST sequence generator designs employ LFSR's as the basis for the generation of the test sequences. Several different techniques have been developed for the construction of the test sequence generators of the BIST designs. For example, in the exhaustive testing scheme, all possible input combinations are generated as the test pattern of the BIST-based sequence generator. This scheme, however, is not suitable for circuitries with requiring large amount of inputs.
In another pseudo-exhaustive testing scheme, the electronic circuitry of the BIST test device is partitioned into a number of smaller sub-circuits. Each of the subcircuits performs its own exhaustive testing procedure as in the exhaustive testing scheme described above. This pseudo-exhaustive testing scheme is limited by the fact that it can not generate deterministic sequences or sequences with repeated test patterns. Such limitation prohibits the use of this pseudo-exhaustive testing scheme in sequential circuits or testing schemes concerning delay faults.
In another pseudo-random testing scheme, a pseudo-random pattern generator is utilized to generate the test patterns in sequences. This scheme, however, is restricted in the detection of some random pattern resistant faults, and is neither suitable for use in sequential circuits nor in the testing scheme concerning delay faults.
In still another mixed-mode testing scheme, pseudo-random test patterns are generated first and then certain test patterns of specific arrangement. The hardware structural configuration of this testing scheme, however, requires much more complication.